package or;

import org.junit.jupiter.api.Test;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class T1631 {

    int[][] dirs = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public int minimumEffortPath(int[][] heights) {
        int m = heights.length;
        int n = heights[0].length;
        Queue<int[]> queue = new PriorityQueue<>((a,b)->a[2]-b[2]);
        queue.offer(new int[]{0, 0, 0});
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }
        dist[0][0] = 0;
        boolean[][] boo = new boolean[m][n];
        while (!queue.isEmpty()) {
            int[] edge = queue.poll();
            int x = edge[0], y = edge[1], d = edge[2];
            if (boo[x][y]) continue;
            if (x == m - 1 && y == n - 1) break;
            boo[x][y] = true;
            for (int i = 0; i < dirs.length; i++) {
                int nx = x + dirs[i][0];
                int ny = y + dirs[i][1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n) {
                    int nd = Math.max(d, Math.abs(heights[x][y] - heights[nx][ny]));
                    if (nd < dist[nx][ny]) {
                        dist[nx][ny] =nd;
                        queue.offer(new int[]{nx,ny,nd});
                    }
                }
            }
        }
        return dist[m-1][n-1];
    }


    @Test
    public void test() {
        Queue<Integer> queue = new PriorityQueue<>((a, b) -> a - b);

        queue.add(2);
        queue.add(1);
        queue.add(3);

        System.out.println(queue.poll());

    }


}
